/*
计数排序（Counting Sort）是一种非比较排序算法，适用于数据范围不大的场景，时间复杂度为 $O(n+k)$，其中 $k$ 表示待排序数组中最大值的大小。
计数排序的基本思想是：对于一个给定的输入序列（待排序的数组），每一个元素要求是非负整数。计数排序的思想是对每一个输入元素 x，确定小于 x 的元素个数。
一旦有了这个信息，就可以将 x 直接存放到输出数组的正确位置上。如果输入元素是重复的，那么每个重复元素都要对应一个正确位置，且重复元素的存放顺序与输入的顺序相同。
稳定
 */

/*
流程如下：
1.找出最大最小值
2.创建长度为最大值减去最小值+1的数组
3.数组统计每个值的出现次数(根据与最小值的差值来决定索引)
4.根据前面的数组，计算每个值的位置
5.遍历 将数值对应到新数组中
 */
function countingSort(arr) {
    const len = arr.length;
    if (len <= 1) {
        return arr;
    }
    //? 找到最大值和最小值
    let max = arr[0];
    let min = arr[0];
    for (let i = 1; i < len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    //? 统计每个值的出现次数
    //?  Array.from(arrayLike, mapFn)arrayLike  是类数组对象或可迭代对象， mapFn  是对数组中每个元素进行操作的函数 此处即生成全为0数组
    const countArr = Array.from({ length: max - min + 1 }, () => 0);

    for (let i = 0; i < len; i++) {
        //? 这里使用arr[i] - min作为索引 指示了该值应该在数组的哪个位置，这个位置记录了其出现次数(因为这个数组的长度是max-min+1)
        countArr[arr[i] - min]++;
    }
    //? 计算每个值的位置
    for (let i = 1; i < countArr.length; i++) {
        //? 计算比该值小或相等的值的个数(countArr[i - 1]就代表i-1索引处值的出现次数 countArr[i]就得到了i索引处值的位置)
        countArr[i] += countArr[i - 1];
    }
    //? 将数值对应到数组中
    const sortedArr = Array.from({ length: len }, () => 0);
    for (let i = len - 1; i >= 0; i--) {
        //? 这里为什么要-1 是因为countArr[arr[i] - min]是从1开始的
        sortedArr[countArr[arr[i] - min] - 1] = arr[i];
        //? 这里的处理是针对重复元素
        countArr[arr[i] - min]--;
    }
    return sortedArr;
}
const arr = [3,5,1,2,8,2,10]
console.log(countingSort(arr))
